package com.fulu.javabase.arithmetic;

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * Given a string s, find the length of the longest substring without repeating characters.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author gu
 */
public class MinLengthWithoutRepeat {
    // 用时过长
    public int lengthOfLongestSubstring(String s) {
        int window = s.length();
        int result = 0;
        for(int i = 0; i< window; i++){
            for(int j = window; j > i && j - i > result; j--){
                String subStr = s.substring(i, j);
                String[] arr = subStr.split("");
                Set<String> set = new HashSet<>(Arrays.asList(arr));
                int length = subStr.length();
                if(set.size() == length && s.contains(subStr)){
                    System.out.println(subStr);
                    if(length > result){
                        result = length;
                    }
                }
            }
        }
        return result;
    }

    public int lengthOfLongestSubstring2(String s) {
        byte[] bytes = s.getBytes();
        int length = 0;
//        LinkedList<Byte> list = new LinkedList<>(); // 5ms
        ArrayList<Byte> list = new ArrayList<>(); // 4ms
        for (int i = 0; i < bytes.length; i++) {
            byte b = bytes[i];
            int idx = list.indexOf(b);
            list.add(b);
            if(idx != -1){
                for (int j = 0; j <= idx; j++) {
                    list.remove(0);
                }
            }
            length = Math.max(length, list.size());
        }
        return length;
    }
    public int lengthOfLongestSubstring3(String s) {
        if(s == null || s.length() < 2){
            return s == null ? 0 : s.length();
        }
        byte[] bytes = s.getBytes();
        int length = 0;
        int pre = 0;
        int rear = 1;
        for (int i = 0; i < bytes.length - 1; i++) {
            for (int j = pre; j < rear ; j++) {
                if(bytes[j] == bytes[rear]){
                    pre = j + 1;
                    break;
                }
            }
            rear++;
            length = Math.max(length, rear - pre);
        }
        return length;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        String s = "pwwkew";
        s = " ";
        int len = new MinLengthWithoutRepeat().lengthOfLongestSubstring3(s);
        long end = System.currentTimeMillis();
        System.out.println("用时" + (end - start));
        System.out.println(len);
    }
}
